import java.util.Arrays;
import java.util.Comparator;
import java.util.Map;
import java.util.PriorityQueue;

public class Not {
    public static void queue(int[] array,int index,int len) {//建立大根堆
        int priov=index;
        int chioe=priov*2+1;
        while(chioe<len) {
            if(chioe+1<len  &&  array[chioe]<array[chioe+1]) {
                chioe++;
            }
            if(array[chioe]>array[priov]) {
                int tmp=array[chioe];
                array[chioe]=array[priov];
                array[priov]=tmp;
                priov=chioe;
                chioe=priov*2+1;
            }else {
                break;
            }
        }
    }
    public static void myqueue(int[] array,int index) {//堆排序
        int tmp=array[0];
        array[0]=array[index];
        array[index]=tmp;
        queue(array,0,index);
    }
    public static void bsInsertSort(int[] array,int left,int right) {//直接插入排序
        for(int i=left+1;i<right;i++) {
            for(int j=i-1;j>=0;j--) {
                int tmp=array[j+1];
                if(tmp<array[j]) {
                    array[j+1]=array[j];
                    array[j]=tmp;
                }else {
                    break;
                }
            }
        }
    }
    public static void swap(int[] array,int left,int right) {//用于快速排序中的三分法，把中间值放到left中
        int tmp=array[left];
        array[left]=array[right];
        array[right]=tmp;
    }
    public static int quickSortInternal(int[] array,int left,int right,int index) {//三分快速排序挖坑法优化
        if(array[left]<array[index]) {
            swap(array,left,index);
        }
        if(array[left]>array[right]) {
            swap(array,left,right);
        }
        if(array[index]>array[right]) {
            swap(array,index,right);
        }
        int tmp=array[left];
        while(right>left) {
            while (array[right]>tmp&&right>left) {
                right--;
            }
            array[left]=array[right];
            while (array[left]<tmp&&right>left) {
                left++;
            }
            array[right]=array[left];
        }

        array[right]=tmp;
        return right;
    }
    public static void quickSort(int[] array,int left,int right) {//快速排序优化
        if(left>right) {
            return;
        }
        int index=(right-left)/2;
        //if(right-left+1<=100) {//每分一个区间，都会越来越趋于有序，到达一定阈值，就可以用直接插入排序，更快；
            //bsInsertSort(array,left,right);
            //return;
        //}

        int priov =quickSortInternal(array, left,right,index);
        quickSort(array,left,priov-1);
        quickSort(array,priov+1,right);
    }
    public static void main(String[] args){
        PriorityQueue<Map.Entry<String,Integer>> ret =new PriorityQueue<>(3, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                return 0;
            }
        });
        

//        TreeSo ret =new TreeSo();
//        ret.charu(15);
//        ret.charu(8);
//        ret.charu(6);
//        ret.charu(13);
//        ret.charu(10);
//        System.out.println(ret.chazhao(11));
//        ret.zhoxu(ret.root);
//        int[] arr={8,4,11,5,99,0,14,54,96,16,75,82,64,45};
//        quickSort(arr,0,arr.length-1);
//        for(int i=(arr.length-1-1)/2;i>=0;i--) {
//            queue(arr,i,arr.length);
//        }
//        for(int i=arr.length-1;i>=0;i--) {
//            myqueue(arr,i);
//        }
//        System.out.println(Arrays.toString(arr));
    }

}
